import copy
from java_book_is_heap import left_child, right_child, parent


def move_down(data, first, last, is_max=True):
    largest = left_child(first)
    while largest <= last:

        # left node or right node is the largest
        # now largest is the left node, and largest + 1 is the right node
        if largest < last:
            if is_max:
                if data[largest] < data[largest + 1]:
                    largest += 1
            else:
                if data[largest] > data[largest + 1]:
                    largest += 1

        is_continue = False
        if is_max:
            if data[first] < data[largest]:
                is_continue = True
        else:
            if data[first] > data[largest]:
                is_continue = True
        if not is_continue:
            largest = last + 1
        else:
            print(data[first], data[largest], '->', end=' ')
            data[first], data[largest] = data[largest], data[first]
            print(data[first], data[largest])
            first = largest
            largest = left_child(first)


def heap_dequeue(data, is_max=True):
    if not len(data):
        return None
    if 0:
        # bad performance
        head = data.pop(0)
        tail = data.pop(-1)
        data.insert(0, tail)
    else:
        head = data[0]
        tail = data.pop(-1)
        data[0] = tail

    n = len(data)
    p = 0

    move_down(data, p, n - 1, is_max=is_max)

    return head


if __name__ == '__main__':

    def main():
        data = [20, 10, 15, 8, 7, 13, 14, 2, 5, 6]
        print(data)

        x = heap_dequeue(data)
        print('dequeue', x)

        print(data)

    main()
